package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 层次遍历, 加右节点
 *
 * @author tzp
 * @since 2020/9/14
 */
public class LC117 implements TreeProblem {
    public static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    ", next=" + next +
                    '}';
        }
    }

    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Deque<Node> queue = new ArrayDeque<>();
        queue.addLast(root);

        Node seperator = root;
        Node pre = null;

        while (queue.size() != 0) {
            Node c = queue.removeFirst();

            if (pre != null) {
                pre.next = c;
            }
            pre = c;

            if (c.left != null) {
                queue.addLast(c.left);
            }
            if (c.right != null) {
                queue.addLast(c.right);
            }

            if (c == seperator && queue.size() != 0) {
                seperator = queue.getLast();
                pre = null;
            }
        }

        return root;
    }

    public static void main(String[] args) {

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node7 = new Node(7);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.right = node7;

        System.out.println(new LC117().connect(node1));
    }
}
